package com.fw.leetcode.greedy;

import com.fw.leetcode.LeetCode;

/**
 * 122. Best Time to Buy and Sell Stock II
 *
 * You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
 *
 * On each day, you may decide to buy and/or sell the stock.
 * You can only hold at most one share of the stock at any time.
 * However, you can buy it then immediately sell it on the same day.
 *
 * Find and return the maximum profit you can achieve.
 *
 * Example 1:
 *  Input: prices = [7,1,5,3,6,4]
 *  Output: 7
 *  Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
 *               Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
 *               Total profit is 4 + 3 = 7.
 *
 * Example 2:
 *  Input: prices = [1,2,3,4,5]
 *  Output: 4
 *  Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
 *               Total profit is 4.
 *
 * Example 3:
 *  Input: prices = [7,6,4,3,1]
 *  Output: 0
 *  Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.
 *
 * Constraints:
 *  1 <= prices.length <= 3 * 10^4
 *  0 <= prices[i] <= 10^4
 */
public class Num_0122 implements LeetCode {

    private interface Solution {
        int maxProfit(int[] prices);

        default void assertExpected(int[] prices, int expected) {
            if (maxProfit(prices) != expected) {
                maxProfit(prices);
            }
        }
    }

    private static class DynamicProgramOptimizeSolution implements Solution {

        @Override
        public int maxProfit(int[] prices) { // 最优：动态规划（数组缩减成单变量）：时O(n) 空O(1)
            /*
             * [6,1,3,2,4,7] -> 7
             *
             * 动态规划
             * - 从后往前推
             * - 从前往后推
             *
             * 1）当天若持有
             * - 1.1）前一天若是卖出了，则当天是在前一天的收益上再支出买入一股，需扣除当天持有股价格，即负债
             * - 1.2）前一天若是继续持有不卖出，则当天是在前一天的收益上无增无减
             * - - - - 即：前一天持有负债，当天继续持有，无卖出买入
             *   hold_profile(i) = Max { sell_profile(i-1) - prices[i], hold_profile(i-1) }
             * 2）当天若卖出
             * - 2.1）前一天若是继续持有不卖出，则当天是在前一天的收益（负债）上再收入卖出一股，需加上当天持有股价格，即收益
             * - 2.2）前一天若是卖出了，则当天是在前一天的收益上无增无减
             * - - - - 即：前一天卖出后无持有，当天再卖出，说明是当天买入的，所以当天买入再卖出相抵消
             *   sell_profile(i) = Max { hold_profile(i-1) + prices[i], sell_profile(i-1) }
             *
             * 其中 Max 操作：剪枝了很多不可能的路径
             * 注：因只与前一次有关，所以能将数组缩减为单个变量，进一步缩小空间复杂度
             */
            int holdProfile = -prices[0]; // 第一天若持有则形成负债，扣除第一天股价
            int sellProfile = 0;
            for (int i = 1; i < prices.length; i++) {
                holdProfile = Math.max(sellProfile - prices[i], holdProfile);
                sellProfile = Math.max(holdProfile + prices[i], sellProfile);
            }
            // 最后一天肯定得卖出（不能持有）才能最大化利益，所以用最后一天卖出收益
            return sellProfile;
        }
    }

    private static class DynamicProgramSolution implements Solution {

        @Override
        public int maxProfit(int[] prices) { // 动态规划（数组）：时O(n) 空O(n)
            /*
             * [6,1,3,2,4,7] -> 7
             *
             * 动态规划
             * - 从后往前推
             * - 从前往后推
             *
             * 1）当天若持有
             * - 1.1）前一天若是卖出了，则当天是在前一天的收益上再支出买入一股，需扣除当天持有股价格，即负债
             * - 1.2）前一天若是继续持有不卖出，则当天是在前一天的收益上无增无减
             * - - - - 即：前一天持有负债，当天继续持有，无卖出买入
             *   hold_profile(i) = Max { sell_profile(i-1) - prices[i], hold_profile(i-1) }
             * 2）当天若卖出
             * - 2.1）前一天若是继续持有不卖出，则当天是在前一天的收益（负债）上再收入卖出一股，需加上当天持有股价格，即收益
             * - 2.2）前一天若是卖出了，则当天是在前一天的收益上无增无减
             * - - - - 即：前一天卖出后无持有，当天再卖出，说明是当天买入的，所以当天买入再卖出相抵消
             *   sell_profile(i) = Max { hold_profile(i-1) + prices[i], sell_profile(i-1) }
             *
             * 其中 Max 操作：剪枝了很多不可能的路径
             */
            int[] holdProfile = new int[prices.length];
            int[] sellProfile = new int[prices.length];
            holdProfile[0] = -prices[0]; // 第一天若持有则形成负债，扣除第一天股价
            for (int i = 1; i < prices.length; i++) {
                holdProfile[i] = Math.max(sellProfile[i-1] - prices[i], holdProfile[i-1]);
                sellProfile[i] = Math.max(holdProfile[i-1] + prices[i], sellProfile[i-1]);
            }
            // 最后一天肯定得卖出（不能持有）才能最大化利益，所以用最后一天卖出收益
            return sellProfile[prices.length-1];
        }
    }

    private static class GreedySolution implements Solution {

        @Override
        public int maxProfit(int[] prices) { // 最优：贪心：时O(n) 空O(1)
            /*
             * 各个 (prices[i] <= prices[i+1]) 的差值求和
             */
            int maxProfit = 0;
            for (int i = 0; i < prices.length - 1; i++) {
                maxProfit += Math.max(0, prices[i+1] - prices[i]);
            }
            return maxProfit;
        }
    }

    private static class MySolution implements Solution {

        @Override
        public int maxProfit(int[] prices) { // 最优：爬坡找最大区间（不算贪心）：时O(n) 空O(1)
            /*
             * 找 (prices[i], prices[j]) 最长的升序序列差
             */
            int maxProfit = 0;
            int startPrice = -1;
            for (int i = 0; i < prices.length - 1; i++) {
                if (prices[i] <= prices[i+1]) {
                    // 寻到第一个爬坡点
                    if (startPrice == -1) {
                        startPrice = prices[i];
                    }
                    // 继续升序寻找最高峰
                } else {
                    // 到达峰顶，若之前是爬坡则计算与谷底的差值利润
                    if (startPrice != -1) {
                        maxProfit += prices[i] - startPrice;
                        startPrice =  -1; // 复位
                    }
                    // 否则继续向后
                }
            }
            if (startPrice != -1) {
                maxProfit += prices[prices.length - 1] - startPrice;
            }
            return maxProfit;
        }
    }

    public static void main(String[] args) {
        Solution solution = new DynamicProgramOptimizeSolution();
        solution.assertExpected(new int[]{6,1,3,2,4,7}, 7);
        solution.assertExpected(new int[]{7,1,5,3,6,4}, 7);
        solution.assertExpected(new int[]{1,2,3,4,5}, 4);
        solution.assertExpected(new int[]{7,6,4,3,1}, 0);
    }
}
